#ifndef LIST_TOOLS_H
#define LIST_TOOLS_H

#include <assert.h>

#include <list>
using std::list;

/**
 * T is a pointer to something that's got operator< .
 */
template<typename T>
class ListTools {

public:
	/**
	 * *T needs to have the operator== for this to be useable.
	 */
	static bool equals(const list<T>& list1, const list<T>& list2) {
		if (list1.size() != list2.size()) {
			return false;
		}

		typename list<T>::const_iterator it1 = list1.begin();
		typename list<T>::const_iterator it2 = list2.begin();
		while(it1 != list1.end()) {
			if (!(**it1 == **it2)) {
				return false;
			}
			++it1;
			++it2;
		}
		assert(it2 == list2.end());

		return true;
	}

	/**
	 * Return true if list1 is lessThan to list2, false otherwise.
	 * A list inferior in size is lessThan. If the lists are of same
	 * size, the elements are compared from the front; the first list
	 * which has an element inferior is lessThan.
	 */
	static bool lessThan(const list<T>& list1, const list<T>& list2) {
		if (list1.size() < list2.size()) {
			return true;
		} else if (list2.size() < list1.size()) {
			return false;
		} else {
			assert(list1.size() == list2.size());

			typename list<T>::const_iterator it1 = list1.begin();
			typename list<T>::const_iterator it2 = list2.begin();
			while(it1 != list1.end()) {
				if ((**it1) < (**it2)) {
					return true;
				} else if ((**it2) < (**it1)) {
					return false;
				}

				++it1;
				++it2;
			}

			assert(it2 == list2.end());

			return false;
		}
	}

	static void sortedInsert(list<T>& l, T element) {
		typename list<T>::iterator it = l.begin();
		while(it != l.end() && **it < *element) {
			++it;
		}

		l.insert(it, element);
	}

	static void sortedMergeIn(list<T>& list1, list<T>& list2) {
		typename list<T>::iterator it1 = list1.begin();
		typename list<T>::iterator it2 = list2.begin();

		while(it1 != list1.end() && it2 !=list2.end()) {
			while(it2 != list2.end() && **it2 < **it1) {
				list1.insert(it1, *it2);
				++it2;
			}
			++it1;
		}

		while(it2 != list2.end()) {
			list1.insert(it1, *it2);
			++it2;
		}
	}
};

#endif	// LIST_TOOLS_H

